Это статья о классах языков для детерминированной машины Тьюринга. Статья о unix-утилите называется nl.

Класс языков L — множество языков, разрешимых на детерминированной машине Тьюринга с использованием ${\displaystyle O(\log(n))}$ дополнительной памяти для входа длиной n.

Класс языков NL — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием ${\displaystyle O(\log(n))}$ дополнительной памяти для входа длиной n.

Примеры:

• ${\displaystyle \{0^{k}1^{k}:k\geq 0\}\in L}$
• Пусть язык ${\displaystyle PATH=\{(G,s,t):G}$ — ориентированный граф в котором есть путь от s до t${\displaystyle \}}$, тогда ${\displaystyle PATH\in NL}$